package com.caoyanan.algorithm.question.zuoTraining.training004.class03;

/**
 * 找到只出现一次的数
 *
 * 给定一个int类型的数组arr，已知除了一种数只出现1次之外，剩下所有的数都出现了k次，如何使用O(1)的额外空间，找到这个数。
 *
 * @author: caoyanan
 * @time: 2021/6/19 18:28
 */
public class Question02_FindAppearOneTimeNumber {

    public static void main(String[] args) {

        System.out.println(findAppearOneTimeNumber(new int[]{3,3,3, 9,9,9, 13,13,13, 7}, 3));
    }

    /**
     * 利用异或的思想，
     * 首先，arr的长度可能大于10^6这种，然后使用一个O(1)的额外空间复杂度，不是说只能用一个变量，而是说可以使用的是常数空间的内存
     *
     * int类型，最多32位，因为2进制32位，大于2进制，少于32位就可以搞定，
     * 准备一个k进制的数， 以32长度的int数组，来存储每一位
     * 然后遍历数组中的每个数，将arr[i]转换为k进制的数，然后加到 对应位上，并模以k
     * 最后把这个数转成10进制， 就得到了只出现1次的数
     *
     * 因为每个数，只要出现了k次，加完后，最后模以k，都被消掉了。只有那个只出现1次的数，会把自己留下来
     * @param arr
     * @param k
     * @return
     */
    private static int findAppearOneTimeNumber(int[] arr, int k) {

        int[] kDecimalNumber = new int[32];
        for (int i = 0; i < arr.length; i++) {
            int currentNumber = arr[i];
            int[] currentKDecimalNumber = new int[32];
            int index = 0;
            while (currentNumber != 0) {
                currentKDecimalNumber[index++] = currentNumber % k;
                currentNumber = currentNumber / k;
            }
            for (int j = 0; j < 32; j++) {
                kDecimalNumber[j] = (kDecimalNumber[j] + currentKDecimalNumber[j]) % k;
            }
        }

        int answer = 0;
        for (int i = 31; i >= 0; i--) {
            answer = answer * k + kDecimalNumber[i];
        }
        return answer;
    }
}
